/// @tags: EGF BinomInversion
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int constexpr G = 3, P = 1004535809, N = 135000, MaxNum = 1e7 + 5;

inline constexpr LL qpow(LL base, int exp = P - 2) {
  LL ans = 1;
  while (exp) {
    if (exp & 1) ans = ans * base % P;
    base = base * base % P;
    exp >>= 1;
  }
  return ans;
}

int constexpr invG = qpow(G);

int cvt[N << 1];

inline int add(int a, int b) {
  a += b;
  return a >= P ? a - P : a;
}

inline int dec(int a, int b) {
  a -= b;
  return a < 0 ? a + P : a;
}

inline void NTT(int *const f, int n, bool typ) {
  for (int i = 1; i < n; ++i)
    if (i < cvt[i]) swap(f[i], f[cvt[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    int mid = i >> 1, w = qpow(typ ? G : invG, (P - 1) / i);
    for (int j = 0; j < n; j += i) {
      LL wk = 1;
      for (int k = 0; k < mid; ++k, wk = wk * w % P) {
        int tmp = f[j + k + mid] * wk % P;
        f[j + k + mid] = dec(f[j + k], tmp);
        f[j + k] = add(f[j + k], tmp);
      }
    }
  }
  if (typ == false) {
    LL inv = qpow(n);
    for (int i = 0; i < n; ++i) f[i] = inv * f[i] % P;
  }
}

int n, m, S, lim, limNum;
int fac[MaxNum], ifac[MaxNum];

inline void prework() {
  limNum = max(n, m);
  fac[0] = 1;
  for (int i = 1; i <= limNum; ++i) fac[i] = (LL)fac[i - 1] * i % P;
  ifac[limNum] = qpow(fac[limNum]);
  for (int i = limNum - 1; i >= 0; --i) ifac[i] = (LL)ifac[i + 1] * (i + 1) % P;
}

inline LL C(int n, int m) { return (LL)fac[n] * ifac[m] % P * ifac[n - m] % P; }

inline LL F(int x) {
  return C(m, x) * fac[n] % P * qpow(ifac[S], x) % P * ifac[n - S * x] % P *
         qpow(m - x, n - S * x) % P;
}

int A[N << 1], B[N << 1];

inline int main() {
  cin >> n >> m >> S;
  lim = min(m, n / S);
  prework();
  for (int i = 0; i <= lim; ++i) {
    A[i] = F(i) * fac[i] % P;
    B[i] = (i & 1) ? P - ifac[i] : ifac[i];
  }
  reverse(A, A + lim + 1);
  int maxl = 1;
  while (maxl <= lim + lim + 2) maxl <<= 1;
  for (int i = 1; i < maxl; ++i) cvt[i] = cvt[i >> 1] >> 1 | (i & 1) * (maxl >> 1);
  NTT(A, maxl, true), NTT(B, maxl, true);
  for (int i = 0; i < maxl; ++i) A[i] = (LL)A[i] * B[i] % P;
  NTT(A, maxl, false);
  reverse(A, A + lim + 1);
  LL ans = 0;
  for (int i = 0, w; i <= lim; ++i) {
    cin >> w;
    ans = add(ans, (LL)A[i] * ifac[i] % P * w % P);
  }
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4491 [HAOI2018] 染色.in", "r", stdin);
  freopen("P4491 [HAOI2018] 染色.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
